package com.frx.sort.heap;

import java.util.Arrays;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/11/11
 * @Time: 10:48
 */
public class MaxHeap {
    int[] arr;
    int count;
    public MaxHeap(){}
    public MaxHeap(int size){
        arr = new int[size];
    }

    /**
     * @desccription 向堆中添加元素
     * @param element
     */
    public void add(int element){
        if (count>=arr.length){
            return;
        }
        arr[count] = element;
        int i=count;
        count++;
        while (getParent(i) >= 0 && arr[i] > arr[getParent(i)]){
            swap(i,getParent(i));
            i = getParent(i);
        }
    }

    /**
     * 删除堆中的元素
     */
    public void removeMax(){
        if (count == 0){
            return;
        }
        arr[0] = arr[arr.length -1];
        count--;
        siftdown(arr,0);
    }


    /**
     * @description 堆的下沉操作
     * @param arr
     * @param n
     */
    public void siftdown(int[] arr,int n){
        int len = arr.length;
        while (true){
            int maxPos = n;
            if ((2*n+1) < len && arr[2*n + 1] > arr[n]){
                maxPos = 2*n+1;
            }
            if ((2*n + 2) < len && arr[2*n+2] > arr[maxPos]){
                maxPos = 2*n +2;
            }
            if (maxPos == n){
                break;
            }
            swap(n,maxPos);
            n = maxPos;
        }
    }

    private int getParent(int index){
        return (index-1)/2;
    }
    private void swap(int a,int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    public static void main(String[] args){
        MaxHeap heap = new MaxHeap(6);
        heap.add(5);
        System.out.println(Arrays.toString(heap.arr));
        heap.add(6);
        System.out.println(Arrays.toString(heap.arr));
        heap.add(4);
        System.out.println(Arrays.toString(heap.arr));
        heap.add(1);
        System.out.println(Arrays.toString(heap.arr));
        heap.add(7);
        System.out.println(Arrays.toString(heap.arr));
        heap.add(2);
        System.out.println(Arrays.toString(heap.arr));
        heap.removeMax();
        System.out.println(Arrays.toString(heap.arr));
    }
}
